/*
Copyright (C) 2011 by the PSVN Research Group, University of Alberta
*/

/*-----------------------------------------------------------------------------------------*
 *	AsterLookahead with Modifications to test Varient Lookahead
 *	Modifications created by Meir Levi And Maor Tal, on behalf of Roni Stern, BGU
 ------------------------------------------------------------------------------------------*/

/*----------- VarientASLAH: Varibles And Definitions For Testing -------------*/
#define OPEN_MODE FILE_MODE // Define the type of input (from file, inside the code or via the terminal)
#define FILE_MODE 1 // Input from file, filename in arg[2]
#define CODE_MODE 2 // Input from inside code, see below
#define TERMINAL_MODE 3 // Input from terminal, when executing


/* To Enable modes, change the value to 1, to disable change to 0*/
#define ASCENDING_K 1 
#define DESCENDING_K 1
#define CONSTANT_K 1
#define LIMITED_ASC_K 1

/* For each enabled mode, choose the testing range */
#define CONSTANT_START 2
#define CONSTANT_END 8

#define ASCENDING_START 4
#define ASCENDING_END 8

#define DESCENDING_START 15
#define DESCENDING_END 20

#define LIMITED_START 3
#define LIMITED_END 10

/* Do not touch */
#define MODE_ASCENDING_K 9
#define MODE_DESCENDING_K 8
#define MODE_CONSTANT_K 7
#define MODE_LIMITED_ASC_K 6
/*-----------------------------------------------------------------------------*/

	
#include <vector>
#include <dlfcn.h>
#include <inttypes.h>
#include <sys/time.h>
#include "astar_data.hpp"
#include "reservoir.hpp"
#include "psvn_game_so.h"
#include "timer.hpp"

extern "C" {
#include "pdb.h"
}

using namespace std;

char* print_bytes(size_t bytes)
{
    static char str[128];
    if (bytes < 1024)
        sprintf(str, "%lub", bytes);
    else if (bytes < 1024*1024)
        sprintf(str, "%lukb", bytes / 1024);
    else if (bytes < 1024*1024*1024)
        sprintf(str, "%lumb", bytes / (1024*1024));
    else
        sprintf(str, "%.2lfgb", (double)bytes / (1024*1024*1024));
    return str;
}

void get_state_space_name(const char* in, char* out)
{
 // strcpy(out,in);  
  const char* str = strrchr(in, '/');
   // if ((*str) == 0)
    //    str = in;
    str++;
    while (*str && (isalpha(*str) || isdigit(*str) || *str=='_')) {
        *out++ = *str++;
    }
    *out = 0;
}

class ChildGenerator
{
public:
    ChildGenerator(const compiled_game_so_t* game, const void* state)
        : m_game(game), m_state(state)
    { 
        init_so_fwd_iter(m_iter, m_game);
    }
    
    bool Generate(void* child)
    {
        if ((m_rule_used = next_so_fwd_iter(m_iter, m_state)) >= 0) {
            apply_so_fwd_rule(m_rule_used, m_state, child, m_game);
            return true;
        }
        return false;
    }

    int Cost() const 
    { return so_fwd_rule_cost(m_rule_used, m_game); }

    const char* RuleName() const 
    { return m_game->fwd_rule_names[m_rule_used]; }

private:
    const compiled_game_so_t* m_game;
    const void* m_state;
    so_func_ptr m_iter;
    int m_rule_used;
};

class PruningChildGenerator
{
public:
    PruningChildGenerator(const compiled_game_so_t* game, 
                          const void* state,
                          int history)
        : m_game(game), m_state(state), m_history(history)
    { 
        init_so_fwd_iter(m_iter, m_game);
    }
    
    bool Generate(void* child, int* child_history)
    {
        while ((m_rule_used = next_so_fwd_iter(m_iter, m_state)) >= 0) {
            if (so_fwd_rule_valid_for_history(m_history, m_rule_used, m_game))
                break;
        }
        if (m_rule_used < 0)
            return false;
        apply_so_fwd_rule(m_rule_used, m_state, child, m_game);
        *child_history = next_so_fwd_history(m_history, m_rule_used, m_game);
        return true;
    }

    int Cost() const 
    { return so_fwd_rule_cost(m_rule_used, m_game); }

    const char* RuleName() const
    { return m_game->fwd_rule_names[m_rule_used]; }

private:
    const compiled_game_so_t* m_game;
    const void* m_state;
    so_func_ptr m_iter;
    int m_rule_used;
    int m_history;
};

//---------------------------------------------------------------------------

bool do_trivial = true;

void* work_stack[64];
void* work_child;
int lookahead_k = 0;
int solution_cost = INT_MAX;

/*-------------------------- VarientASLAH: Varibles ----------------------------*/
int ascendingK=1;
int constantK=1;
int descendingK=1;
int limitedK=1;
int lookahead_mode=1;
/*------------------------------------------------------------------------------*/

int64_t expanded_nodes; 
int64_t stored_nodes;
int64_t trivial_nodes;
int64_t duplicate_nodes;
int64_t lookahead_nodes;
int64_t memory_used;

int Heuristic(const void* state, const pdb_t* pdb, 
              const compiled_game_so_t* game)
{
    if (is_so_goal(state, game))
        return 0;
    int epsilon = cost_of_cheapest_so_fwd_rule(game);
    int h = 0;
    if (pdb != NULL)
        h = pdb_lookup(pdb, state, game);
    return std::max(epsilon, h);
}

void Lookahead(const compiled_game_so_t* game, const pdb_t* pdb,
               const void* state, const int history, 
               const int current_g, int* min_frontier_cost, 
               const int lookahead_limit, const int d)
{
    // for (int i = 0; i < d; ++i)
    //     printf("  ");
    //print_so_state(stdout, state, game); printf("\n");
    assert(d < 64);
    void* child = work_stack[d];
    int child_history;
    PruningChildGenerator generator(game, state, history);
    while (generator.Generate(child, &child_history)) {
        lookahead_nodes++;
        const int child_g = current_g + generator.Cost();
        const int child_h = Heuristic(child, pdb, game);
        const int child_f = child_g + child_h;
        // for (int i = 0; i < d; ++i)
        //     printf("  ");
        // printf("g=%d, h=%d, f=%d\n", child_g, child_h, child_f);
        if (child_f <= lookahead_limit) {
            if (child_h == 0 && child_f < solution_cost
                && is_so_goal(child, game)) 
            {
                // found a new solution!
                solution_cost = child_f;
                //printf("SOLUTION %d!\n", solution_cost);
                if (child_f < *min_frontier_cost)
                    *min_frontier_cost = child_f;
            } 
            else
                Lookahead(game, pdb, child, child_history, 
                          child_g, min_frontier_cost, 
                          lookahead_limit, d+1);
        } else {
            // outside limit: check if a new minimum frontier node
            if (child_f < *min_frontier_cost)
                *min_frontier_cost = child_f;
        }
    }
}


/*-------------------------- VarientASLAH: Varient functions ----------------------------*/
int ascending(const StateData* current_data){
	return (current_data->depth)/ascendingK;
}

int desending(const StateData* current_data){
	int res = descendingK - current_data->depth;
	if (res>0)
		return res;
	return 1;
}
int limitAscending(const StateData* current_data){
	int res=current_data->depth;
	if (res>limitedK)
			res=limitedK;
	return res;
}

int constant(){
	return constantK;
}

int variant_lookahead(const StateData* current_data){
	if (current_data==NULL) 
		return 1;
	
	if (lookahead_mode == MODE_ASCENDING_K)
		return ascending(current_data);
		
	if (lookahead_mode == MODE_DESCENDING_K)
		return desending(current_data);
	
	if (lookahead_mode == MODE_CONSTANT_K)
		return constant();
		
	if (lookahead_mode == MODE_LIMITED_ASC_K)
		return limitAscending(current_data);
		
	return 1;
}

/*-----------------------------------------------------------------------------*/


void Expand(const compiled_game_so_t* game, const pdb_t* pdb, 
            const StateData& current_data, Reservoir& pool, AStarData& data)
{
    //const int lookahead_limit = current_data.G() + current_data.StaticH() + lookahead_k;

     const int lookahead_limit = current_data.G() + current_data.StaticH() + variant_lookahead(&current_data);

    // printf("expand ");
    // print_so_state(stdout, current_data.State(), game);
    // printf(" g=%d h=%d hs=%d index=%d sc=%d\n", current_data.G(), 
    //        current_data.H(),  current_data.StaticH(), current_data.m_index,
    //        solution_cost);
    
    ChildGenerator generator(game, current_data.State());
    while (generator.Generate(work_child)) {
        const int64_t child_hash = hash_so_state(work_child, game);
        const int child_g = current_data.G() + generator.Cost();
        StateData* child_ptr = data.GetPointer(child_hash);
        
        //child_ptr->depth = current_data.depth + 1;
        //printf("Current depth = %d\n",child_ptr->depth);
        //printf("Current depth = %d\n",current_data.depth);
        
        // printf("  ");
        // print_so_state(stdout, work_child, game);
        // printf("\n");

        if (child_ptr != NULL) {
			//printf("Current depth = %d\n",child_ptr->depth);
            if (child_g >= child_ptr->m_g) {
                // already know a better way to get to this child, skip
                continue;
            }
            if (child_g + child_ptr->m_h >= solution_cost) {
                // child is not better than current solution, skip
                continue;
            }
            // since new g < old g, this new result will occupy a
            // different position in open list; mark old position
            // as stale if it is still in open list.
            if (child_ptr->m_index != -1) {
                data.RemoveFromOpen(child_ptr->m_g + child_ptr->m_h,
                                    child_ptr->m_g, 
                                    child_ptr->m_index);
                child_ptr->m_index = -1;
            }
            // update g and parent for this child
            child_ptr->m_g = child_g;
            child_ptr->m_came_from = current_data.State();
        } 
        else if (is_so_goal(work_child, game)) {
            solution_cost = std::min(solution_cost, child_g);
            //printf("solution! %d\n", child_g);
            continue;
        }
        else {
            // new child; compute static h and store data
            void* new_child = pool.Get(game->state_size);
            copy_so_state(new_child, work_child, game);
            StateData cdata(new_child, current_data.State(), child_g, 
                            Heuristic(new_child, pdb, game),current_data.depth+1);
            child_ptr = data.AddData(child_hash, cdata);
            stored_nodes++;
        }
        // printf("  ");
        // print_so_state(stdout, work_child, game);
        // printf(" g=%d h=%d hs=%d sc=%d\n", child_ptr->G(), child_ptr->H(),
        //        child_ptr->StaticH(), solution_cost);
        
        if (do_trivial && 
            (child_ptr->m_g + child_ptr->m_h <= 
             current_data.m_g + current_data.m_h))
        {
            // perform trivial expansion:
            // simply expand this child without placing it
            // on the open list
            trivial_nodes++;
            const StateData child_data = *child_ptr;
            //printf("trivial ");
            Expand(game, pdb, child_data, pool, data);
        }
        else 
        {
            // perform limited lookahead from child
            int min_frontier_cost = INT_MAX;
            // printf("lookahead ");
            // print_so_state(stdout, work_child, game);
            // printf("\n");

            Lookahead(game, pdb, work_child, 0, child_g, &min_frontier_cost,lookahead_limit, 0);
            
            // update h and add to open list
            child_ptr->m_h = min_frontier_cost - child_g;
            assert(child_ptr->m_static_h <= child_ptr->m_h);
            child_ptr->m_index 
                = data.AddToOpen(child_hash, 
                                 child_ptr->m_g + child_ptr->m_h, 
                                 child_ptr->m_g);
        }
    }
}

int AStarLookahead(const compiled_game_so_t* game, const pdb_t* pdb, 
                   const void* start_state)
{
    if (is_so_goal(start_state, game))
        return 0;

    Reservoir pool(16);
    work_child = pool.Get(game->state_size);
    for (int i = 0; i < 64; ++i)
        work_stack[i] = pool.Get(game->state_size);

    solution_cost = INT_MAX;
    lookahead_nodes = 0;
    expanded_nodes = 0;
    stored_nodes = 0;
    trivial_nodes = 0;

    AStarData data;
    {
        int static_h = Heuristic(start_state, pdb, game);
        if (lookahead_k > 0) {
            int min_frontier_cost = INT_MAX;
            Lookahead(game, pdb, start_state, 0, 0, &min_frontier_cost, 
                      static_h + lookahead_k, 0);
            //printf("min_frontier_cost=%d\n", min_frontier_cost);
        }
        int64_t hash = hash_so_state(start_state, game);
        data.AddData(hash, StateData(start_state, 0, 0, static_h,1), 
                     static_h, static_h);
    }
    while (!data.OpenListEmpty()) {
        int64_t current_hash;
        StateData current_data;
        data.Pop(current_hash, current_data);

        // print_so_state(stdout, current_data.State(), game);
        // printf(" f=%d g=%d h=%d %d\n", current_data.G() + current_data.H(), 
        //        current_data.G(), current_data.H(), solution_cost);

        if (current_data.G() + current_data.H() >= solution_cost)
            // Everything left on queue is worse than current solution
            break;

        expanded_nodes++;
        Expand(game, pdb, current_data, pool, data);
    }
    memory_used = data.Memory() + stored_nodes*game->state_size;
    return solution_cost;
}


void execute(compiled_game_so_t *game, void* pdb, void *state)
{
	int d;
	
	lookahead_k = variant_lookahead(NULL);

	Timer instance_timer;
	d = AStarLookahead( game, (pdb_t*)pdb, state);
	assert(d != INT_MAX);

	printf("elapsed\t%0.3lf",instance_timer.Elapsed()); 
	printf("\tcost %d\texpanded\t%lu",d, expanded_nodes);
	printf("\tlookahead\t%lu",lookahead_nodes);
	printf("\ttrivial\t%lu ",trivial_nodes);
	printf("\tstored\t%lu",stored_nodes);
	printf("\tmemory_used:\t%s\n", print_bytes(memory_used));
	//total_expanded += expanded_nodes;
	//total_trivial += trivial_nodes;
	//total_stored += stored_nodes;
	//total_lookahead += lookahead_nodes;
}



int main( int argc, char **argv )
{
    int i,j,numberOfProblemsInsertedInCode;
    void *so_handle, *state;
    //int64_t total_expanded, total_trivial, total_stored, total_lookahead;
    compiled_game_so_t *game;
    void* pdb;
    char line[4096];
    FILE *fr;            /* declare the file pointer */

    /* read the game */
    if( argc < 2 ) {
        fprintf( stderr, "usage: astar_so state.so k [pdb]\n" );
        exit( EXIT_FAILURE );
    }
    so_handle = dlopen( argv[1], RTLD_LAZY );
    if( so_handle == NULL ) {
        fprintf( stderr, "could not open shared object %s: %s\n",
                 argv[ 1 ], dlerror() );
        exit( EXIT_FAILURE );
    }
    char name[1024];
    get_state_space_name(argv[1], name);
    game = (compiled_game_so_t*)dlsym(so_handle, name);
    if (game == NULL) {
        game = (compiled_game_so_t*)dlsym( so_handle, "psvn_state_space" );
        if( game == NULL ) {
            fprintf( stderr, "could not read game object from %s\n", argv[1]);
            exit( EXIT_FAILURE );
        }
    }

    /* read the pdb */
    if( argc > 3 ) {
        pdb = read_pdb( argv[3], game );
        if (pdb == NULL)
            return EXIT_FAILURE;
    } else {
        pdb = NULL;
    }
    
    state = new_so_state( game );
    Timer total_timer;


	switch(OPEN_MODE){
		case(FILE_MODE):
			fr = fopen(argv[2],"rt");
			if(fr==NULL){
				printf("ERROR while opening file\n");
				printf("Usage: ./val_so ./<problem name> <input file>\n");
				exit(1);
			}
			break;
		case(TERMINAL_MODE):
			printf("Type problem:\n");
			while (fgets( line, 4096, stdin ) == NULL)
				printf("Try again:\n");
			break;
		case(CODE_MODE): /* VarientASLAH: Insert problem directly here */
			strcpy(line,"1 2 B 3 7 8 6 4 5 14 10 12 9 13 11 15");
			numberOfProblemsInsertedInCode = 1;
			break;
	}

	i=0;
	while(	((OPEN_MODE==CODE_MODE) && (i<numberOfProblemsInsertedInCode)) ||
		((OPEN_MODE==FILE_MODE)) || (OPEN_MODE==TERMINAL_MODE))
	{
		/* VarientASLAH Next problem */
		i++;  // OPEN_MODE==CODE
		if (fgets(line,40,fr)==NULL) break;

		while((OPEN_MODE==FILE_MODE) && strlen(line)<38) // OPEN_MODE==FILE
			if((OPEN_MODE==FILE_MODE) && (fgets(line,40,fr)==NULL)) // OPEN_MODE==FILE
				break;
		
				
		if (read_so_state( line, state, game ) <= 0)
			break;	
							
		printf("\n\n~~~~~NEW PROBLEM: %s\n",line);
		
		if (CONSTANT_K){
			lookahead_mode = MODE_CONSTANT_K;
			for(j=CONSTANT_START; j<=CONSTANT_END ;j++){
				constantK = j;
				printf("Lookahead = %d\n",j);
				execute(game,pdb,state);
			}
		}
		

		if (DESCENDING_K){
			lookahead_mode = MODE_DESCENDING_K;
			for(j=DESCENDING_START; j<=DESCENDING_END ;j++){
				descendingK = j;
				printf("Lookahead = %d - Depth\n",j);
				execute(game,pdb,state);
			}
		}


		if (LIMITED_ASC_K){
			lookahead_mode = MODE_LIMITED_ASC_K;
			for(j=LIMITED_START; j<=LIMITED_END ;j++){
				limitedK = j;
				printf("Lookahead = Depth, limited to %d\n",j);
				execute(game,pdb,state);
			}
		}

						
		if (ASCENDING_K){
			lookahead_mode = MODE_ASCENDING_K;
			for(j=ASCENDING_START; j<=ASCENDING_END ;j++){
				ascendingK = j;
				printf("Lookahead = Depth / %d\n",j);
				execute(game,pdb,state);
			}
			
		}
		
		if (OPEN_MODE==TERMINAL_MODE)
			break;			
	}			
	
    destroy_so_state( state );
    if( pdb != NULL )
        destroy_pdb( (pdb_t*)pdb, game );
    double elapsed = total_timer.Elapsed();
    return 0;
}

